Computing and communication networks typically include network devices, such as routers, firewalls, switches, or gateways, which transfer or switch data, such as packets, from one or more sources to one or more destinations. Network devices may operate on the packets as the packets traverse the network, such as by forwarding or filtering the packet-based network traffic.
A network device may schedule traffic for delivery to one or more destinations based on a variety of mechanisms. One scheduling mechanism is a weighted round robin (WRR) scheduler. In WRR scheduling, each packet flow or connection has its own packet queue in a network device. WRR scheduling is the simplest approximation of generalized processor sharing (GPS). While GPS serves infinitesimal amounts of data from each nonempty queue, WRR serves a number of packets for each nonempty queue. The WRR scheduling hierarchy is usually maintained in a tree structure with a root node at the top, leaf nodes at the bottom, and intermediate nodes in between. If the scheduling hierarchy has only one level (i.e., if there is no intermediate nodes between the root node and leaf nodes), it is called a 1-level (or “flat”) WRR scheduling hierarchy. If the scheduling hierarchy has one level of intermediate nodes between the root node and leaf nodes, it is called a 2-level WRR scheduling hierarchy. In general, an N-level WRR scheduling hierarchy corresponds to a scheduling hierarchy that includes N−1 levels of intermediate nodes. A regular N-level WRR scheduler assigns a static weight to each node in the scheduling hierarchy (e.g., other than the root node) and each node (e.g., other than the root node) may maintain a running weight credit. A regular flat WRR scheduler maintains a running weight credit per leaf node of a tree structure which has no intermediate nodes.
A regular 2-level WRR scheduler maintains a running weight credit per leaf node and per intermediate node of a tree structure. An enqueue (Enq) thread traverses the tree structure bottom-up, a dequeue (Deq) thread traverses the tree structure top-down, and other threads may also be used by the 2-level WRR scheduler. The dequeue thread resolves a selected intermediate node first, performs a WRR across other intermediate nodes, moves to leaf nodes, and performs another WRR across the leaf nodes that are attached to the selected intermediate node. A leaf node may be allocated a bandwidth of: total_throughput×ratio_intermediate×ratio_leaf. The “total_throughput” may be a total throughput of a root node (e.g., of the tree structure). The “ratio_intermediate” may be a relative weight that indicates a percentage of the total throughput that may be allocated to an intermediate node. The “ratio_leaf” may be a relative weight that indicates a percentage of the total throughput (e.g., of a corresponding intermediate node) that may be allocated to a leaf node. All the weights for nodes may be statically configured.
Using a 2-level WRR scheduler, as opposed to a 1-level WRR scheduler, adds complexity to a scheduling mechanism. Besides the added complexity going from a 1-level WRR scheduler to a 2-level WRR scheduler, certain traffic may require different functionality than provided by a 2-level WRR scheduler. For example, traffic may require throughput that is allocated fairly across active leaf nodes, but such a requirement may only be provided by a 1-level WRR scheduler (e.g., rather than a 2-level WRR scheduler).